Procedimento de Chien
Este artigo ou secção contém uma lista de referências no fim do texto, mas as suas fontes não são claras porque não são citadas no corpo do artigo, o que compromete a confiabilidade das informações. (Agosto de 2020) |
Na álgebra abstrata, o procedimento de Chien, cujo nome advém de R. T. Chien, é um algoritmo rápido para determinar a raiz de um polinómio definido sobre um corpo finito. O caso mais típico para a utilização do procedimento de Chien é no cálculo das raízes de polinómios error-locator encontrados na descodificação do código de Reed-Solomon e código de BCH.
Algoritmo
[editar | editar código-fonte]Denotando o polinómio (sobre o corpo finito GF()) cujas raízes queremos determinar como:
Conceptualmente, podemos avaliar por cada não-zero em GF(). Aqueles que resultarem em 0 são raízes do polinómio.
O procedimento de Chien é baseado em duas observações:
- Cada não-zero pode ser expresso como para alguns , onde é um elemento primitivo (sugerido do inglês, primitive element) de , é a potência do elemento primitivo . Assim as potências por cada cobrem o espectro inteiro (excluindo o elemento zero).
- A seguinte relação existe:
Por outras palavras podemos definir cada como a soma de um conjunto de termos , dos quais o próximo conjunto de coeficiente pode ser derivado, e assim:
Desta maneira podemos começar em com , e iterar através de cada valor de até . Se em qualquer altura a soma resultante é zero, temos:
assim também, logo é uma raiz. Desta maneira confirmamos todos os elementos no espectro.
Quando implementado em hardware esta aproximação reduz significativamente a complexidade, dado que todas as multiplicações consistem numa variável e uma constante, ao invés de duas variáveis como num aproximação bruta.
Referências
[editar | editar código-fonte]- Chien, R. T. (outubro 1964), «Cyclic Decoding Procedures for the Bose-Chaudhuri-Hocquenghem Codes», IEEE Transactions on Information Theory, ISSN 0018-9448, IT-10 (4): 357–363
- Lin, S.; Costello, D. (2004), Error Control Coding: Fundamentals and Applications, Englewood Cliffs, NJ: Prentice-Hall
- Gill, John, EE387 Notes #7, Handout #28 (PDF), Stanford University, pp. 42–45, consultado em 21 de abril de 2010